#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_FRAMES 10
#define MAX_PAGES 100

// 函数声明
void fifo(int pages[], int n, int frames);      // 先进先出
void lru(int pages[], int n, int frames);       // 最近最少使用
void opt(int pages[], int n, int frames);       // 最佳置换
void clock(int pages[], int n, int frames);     // 时钟算法
int find_farthest_use(int pages[], int n, int index, int frames[], int frame_count);    // 查找最长时间不被使用的页面

int main() {
    int pages[MAX_PAGES];
    int n, frames;
    int choice;
    
    printf("请输入页面引用序列长度: 12\n");
    n = 12;
    // scanf("%d", &n);
    
    int t_pages[] = {2,3,2,1,5,2,4,5,3,2,5,2};

    printf("请输入页面引用序列: 2,3,2,1,5,2,4,5,3,2,5,2\n");
    for(int i = 0; i < n; i++) {
        pages[i] = t_pages[i];
        // scanf("%d", &pages[i]);
    }
    
    printf("请输入物理内存帧数: 3");
    frames = 3;
    // scanf("%d", &frames);
    
    while(1) {
        printf("\n页面置换算法菜单:\n");
        printf("1. FIFO (先进先出)\n");
        printf("2. LRU (最近最少使用)\n");
        printf("3. OPT (最佳置换)\n");
        printf("4. Clock (时钟算法)\n");
        printf("5. 退出\n");
        printf("请选择算法: ");
        scanf("%d", &choice);
        
        switch(choice) {
            case 1:
                fifo(pages, n, frames);
                break;
            case 2:
                lru(pages, n, frames);
                break;
            case 3:
                opt(pages, n, frames);
                break;
            case 4:
                clock(pages, n, frames);
                break;
            case 5:
                exit(0);
            default:
                printf("无效选择!\n");
        }
    }
    
    return 0;
}

// FIFO算法实现
void fifo(int pages[], int n, int frames) {
    int frame[MAX_FRAMES];      // 物理块中存放的页帧
    int queue[MAX_FRAMES];      // 先来后到的顺序
    int front = 0, rear = 0;
    int page_faults = 0;
    
    for(int i = 0; i < frames; i++) {
        frame[i] = -1; // 初始化帧为-1表示空
    }
    
    printf("\nFIFO页面置换过程:\n");
    
    for(int i = 0; i < n; i++) {
        bool page_found = false;
        
        // 检查页面是否已在内存中
        for(int j = 0; j < frames; j++) {
            if(frame[j] == pages[i]) {
                page_found = true;
                break;
            }
        }
        // 如果不在内存中
        if(!page_found) {
            page_faults++;
            
            if(rear < frames) {
                // 还有空闲帧
                frame[rear] = pages[i];
                queue[rear] = pages[i];
                rear++;
            } else {
                // 替换最早进入的页面
                int replace_page = queue[front];
                
                for(int j = 0; j < frames; j++) {
                    if(frame[j] == replace_page) {
                        frame[j] = pages[i];
                        break;
                    }
                }
                
                // 更新队列
                queue[front] = pages[i];
                front = (front + 1) % frames;
            }
            
            // 打印当前内存状态
            printf("缺页 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        } else {
            printf("命中 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        }
    }
    
    printf("\nFIFO算法总缺页次数: %d\n", page_faults);
}

// LRU算法实现
void lru(int pages[], int n, int frames) {
    int frame[MAX_FRAMES];      // 物理块中存放的页帧
    int time[MAX_FRAMES];       // 物理块中的页帧最近使用的时间
    int page_faults = 0;
    
    for(int i = 0; i < frames; i++) {
        frame[i] = -1;
        time[i] = -1;
    }
    
    printf("\nLRU页面置换过程:\n");
    
    for(int i = 0; i < n; i++) {
        bool page_found = false;
        int pos = -1;
        
        // 检查页面是否已在内存中
        for(int j = 0; j < frames; j++) {
            if(frame[j] == pages[i]) {
                page_found = true;
                pos = j;
                break;
            }
        }
        // 如果在内存中
        if(page_found) {
            time[pos] = i; // 更新最近使用时间
            printf("命中 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        } else {
            page_faults++;
            
            // 查找最近最少使用的页面
            int lru_time = INT_MAX;
            int replace_pos = 0;
            // 找使用时间最早的页帧，如果有空闲位置则必定是空闲位置
            for(int j = 0; j < frames; j++) {
                if(time[j] < lru_time) {
                    lru_time = time[j];
                    replace_pos = j;
                }
            }
            
            // 替换页面
            frame[replace_pos] = pages[i];
            time[replace_pos] = i;
            
            // 打印当前内存状态
            printf("缺页 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        }
    }
    
    printf("\nLRU算法总缺页次数: %d\n", page_faults);
}

// OPT算法实现
void opt(int pages[], int n, int frames) {
    int frame[MAX_FRAMES];
    int page_faults = 0;
    
    for(int i = 0; i < frames; i++) {
        frame[i] = -1;
    }
    
    printf("\nOPT页面置换过程:\n");
    
    for(int i = 0; i < n; i++) {
        bool page_found = false;
        
        // 检查页面是否已在内存中
        for(int j = 0; j < frames; j++) {
            if(frame[j] == pages[i]) {
                page_found = true;
                break;
            }
        }
        
        if(page_found) {
            printf("命中 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        } else {
            page_faults++;
            
            // 查找空闲帧
            bool has_empty = false;
            for(int j = 0; j < frames; j++) {
                if(frame[j] == -1) {
                    frame[j] = pages[i];
                    has_empty = true;
                    break;
                }
            }
            
            if(!has_empty) {
                // 查找将来最长时间不会被使用的页面
                int farthest = find_farthest_use(pages, n, i, frame, frames);
                
                // 替换页面
                for(int j = 0; j < frames; j++) {
                    if(frame[j] == farthest) {
                        frame[j] = pages[i];
                        break;
                    }
                }
            }
            
            // 打印当前内存状态
            printf("缺页 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d ", frame[j]);
                else
                    printf("- ");
            }
            printf("]\n");
        }
    }
    
    printf("\nOPT算法总缺页次数: %d\n", page_faults);
}

// Clock算法实现
void clock(int pages[], int n, int frames) {
    int frame[MAX_FRAMES];
    int use_bit[MAX_FRAMES];
    int pointer = 0;
    int page_faults = 0;
    
    for(int i = 0; i < frames; i++) {
        frame[i] = -1;
        use_bit[i] = 0;
    }
    
    printf("\nClock页面置换过程:\n");
    
    for(int i = 0; i < n; i++) {
        bool page_found = false;
        
        // 检查页面是否已在内存中
        for(int j = 0; j < frames; j++) {
            if(frame[j] == pages[i]) {
                page_found = true;
                use_bit[j] = 1; // 设置使用位
                break;
            }
        }
        
        if(page_found) {
            printf("命中 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d(%d) ", frame[j], use_bit[j]);
                else
                    printf("- ");
            }
            printf("] 指针位置: %d\n", pointer);
        } else {
            page_faults++;
            
            // 查找替换页面
            while(true) {
                if(use_bit[pointer] == 0) {
                    // 找到替换页面
                    frame[pointer] = pages[i];
                    use_bit[pointer] = 1;
                    pointer = (pointer + 1) % frames;
                    break;
                } else {
                    // 给第二次机会
                    use_bit[pointer] = 0;
                    pointer = (pointer + 1) % frames;
                }
            }
            
            // 打印当前内存状态
            printf("缺页 %d -> 内存: [", pages[i]);
            for(int j = 0; j < frames; j++) {
                if(frame[j] != -1)
                    printf("%d(%d) ", frame[j], use_bit[j]);
                else
                    printf("- ");
            }
            printf("] 指针位置: %d\n", pointer);
        }
    }
    
    printf("\nClock算法总缺页次数: %d\n", page_faults);
}

// 辅助函数：查找将来最长时间不会被使用的页面
int find_farthest_use(int pages[], int n, int index, int frames[], int frame_count) {
    int farthest = -1;
    int farthest_distance = -1;
    
    for(int i = 0; i < frame_count; i++) {
        int distance = 0;
        bool found = false;
        
        for(int j = index + 1; j < n; j++) {
            if(pages[j] == frames[i]) {
                distance = j - index;       // 被使用时到现在的距离
                found = true;   // 将来使用了这个页面
                break;
            }
        }
        
        if(!found) {
            return frames[i]; // 这个页面将来不会再被使用
        }
        // 找最远被使用的那个页面
        if(distance > farthest_distance) {
            farthest_distance = distance;
            farthest = frames[i];
        }
    }
    
    return farthest;
}